package leetcode.editor.vip.solution694;

import java.util.HashSet;
import java.util.Set;

public class Solution694 {
    // 题目描述：https://labuladong.gitee.io/algo/4/31/108/#不同的岛屿数量

    int m, n;

    // 大体思路：遍历岛屿的时候使用 1，2，3，4代表上下左右，-1,-2,-3,-4代表撤销
    // 为啥需要代表撤销，例如：24，可以24一起走完，也可以先走2，返回之后再走4，所以需要一个撤销来标识
    // 将岛屿表示为字符串之后，在进行Set去重，就知有多少种岛屿
    int numDistinctIslands(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        Set<String> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                StringBuilder sb = new StringBuilder();
                // 初始的方向可以随便写，不影响正确性
                dfs(grid, i, j, sb, 0);
                // 使用set去重
                set.add(sb.toString());
            }
        }

        return set.size();
    }

    public void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return;

        grid[i][j] = 0;
        // 记录添加操作
        sb.append(dir + ",");

        dfs(grid, i - 1, j, sb, 1); // 上
        dfs(grid, i + 1, j, sb, 2); // 下
        dfs(grid, i, j - 1, sb, 3); // 左
        dfs(grid, i, j + 1, sb, 4); // 右

        // 记录撤销操作
        sb.append(-dir + ",");
    }

}
